package zcw.com.lib_leet_code;

/**
 * Created by 朱城委 on 2021/8/16.<br><br>
 *
 * 中等：最长回文子串
 */
public class Topic5 {
    public static void main(String[] args) {
        Topic5 instance = new Topic5();

        instance.init();
        System.out.println(instance.longestPalindrome("babad"));

        instance.init();
        System.out.println(instance.longestPalindrome("cbbd"));

        instance.init();
        System.out.println(instance.longestPalindrome("a"));

        instance.init();
        System.out.println(instance.longestPalindrome("ac"));

        instance.init();
        System.out.println(instance.longestPalindrome("aaaaa"));
    }

    public String longestPalindrome(String s) {
        if(s.length() < 2) {
            return s;
        }

        int startIndex = 0;
        int maxLen = 1;
        char[] array = s.toCharArray();
        boolean[][] temp = new boolean[array.length][array.length];

        for(int i = 0; i < array.length; i++) {
            temp[i][i] = true;

            if(i < array.length - 1 && array[i] == array[i + 1]) {
                temp[i][i + 1] = true;
                startIndex = i;
                maxLen = 2;
            }
        }

        for(int len = 3; len <= array.length; len++) {
            for(int j = 0; j <= array.length - len; j++) {
                int i = j + len - 1;
                if(temp[j + 1][i - 1] && array[j] == array[i]) {
                    temp[j][i] = true;
                    startIndex = j;
                    maxLen = len;
                }
            }
        }

        return s.substring(startIndex, startIndex + maxLen);
    }

    private int startIndex = 0;
    private int maxLen = 0;

    public String longestPalindrome2(String s) {
        if(s.length() < 2) {
            return s;
        }

        char[] array = s.toCharArray();
        for(int i = 0; i < array.length; i++) {
            helper(array, i, i);
            helper(array, i, i + 1);
        }

        return s.substring(startIndex, startIndex + maxLen);
    }

    private void helper(char[] array, int i, int j) {
        while (i >= 0 && j < array.length && array[i] == array[j]) {
            i--;
            j++;
        }

        int counter = j - i - 1;
        if(counter > maxLen) {
            maxLen = counter;
            startIndex = i + 1;
        }
    }

    private void init() {
        startIndex = 0;
        maxLen = 0;
    }
}
